class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=2:return 0
        primes = [True] * n
        count = 0
        for i in range(2, n):
            if primes[i]:
                count += 1
                for j in range(i*2, n, i):
                    primes[j]=False
        return count

print(Solution().countPrimes(3))